package com.chapter4.graph.sp;

import java.util.Stack;

/**
 * 
* @ClassName: BellmanFordSP 
* @Description:Bellman_Ford的最短路径算法
* 
* 对每个边进行relax操作，重复V轮
*  
* @author minjun
* @date 2015年3月15日 下午3:12:18 
*
 */
public class BellmanFordSP {
	
	private double[] distTo;
	
	private DirectEdge[] edgeTo;

	public BellmanFordSP(DirectWeightGraph g,int s){
		distTo=new double[g.V()];
		edgeTo=new DirectEdge[g.V()];
		for(int i=0;i<g.V();i++){
			distTo[i]=Double.POSITIVE_INFINITY;
		}
		distTo[s]=0.0;
		
		for(int i=0;i<g.V();i++){
			for(int j=0;j<g.V();j++){
				relax(g,j);
			}
		}
	}
	
	/**
	 * 
	* @Title: hasNegativeCycle 
	* @Description: 是否有负环路
	* @param @return    设定文件 
	* @return boolean    返回类型 
	* @throws
	 */
	public boolean hasNegativeCycle(){
		return false;
	}
	
	/**
	 * 
	* @Title: negativeCycle 
	* @Description: 列出一个负环路 
	* @param @return    设定文件 
	* @return Iterable<DirectEdge>    返回类型 
	* @throws
	 */
	public Iterable<DirectEdge> negativeCycle(){
		return null;
	}

	private void relax(DirectWeightGraph g, int v) {
		for(DirectEdge edge:g.adj(v)){
			int w=edge.to();
			if(distTo[w]>distTo[v]+edge.weight()){
				distTo[w]=distTo[v]+edge.weight();
				edgeTo[w]=edge;
			}
		}
	}
	
	public boolean hasPathTo(int v){
		return distTo[v]<Double.POSITIVE_INFINITY;
	}
	
	public Iterable<DirectEdge> pathTo(int v){
		Stack<DirectEdge> stack=new Stack<DirectEdge>();
		for(DirectEdge edge=edgeTo[v];edge!=null;edge=edgeTo[edge.from()]){
			stack.push(edge);
		}
		
		Stack<DirectEdge> edges=new Stack<DirectEdge>();
		while(!stack.isEmpty()){
			edges.push(stack.pop());
		}
		return edges;
	}

	public double distTo(int v) {
		return distTo[v];
	}
}
